1. Field of the Invention
This invention relates generally to network processor devices, routers, and the like and, more specifically, to a packet forwarding table and packet routing method which provides multiple next hop options for a single forwarding entry and the ability to weight the probability with which each next hop is to be chosen.
2. Discussion of the Prior Art
Traditional packet routing capability provided in network processor devices, routers, switches, and the like, typically utilize a network routing table having entries which provide a single next hop for each table entry. FIG. 1 depicts a typical network routing scenario 10. To route a packet from System C 13 to System 3 indicated as element 18 in FIG. 1, a traditional packet forwarding table would provide one path (e.g., via router R2) from router R5 to R1. In the example network routing scenario of FIG. 1, it would be desirable to have the ability to route through R3 as well, or possibly even through R4.
In general, in a network processor, the ability to provide multiple next hop options coupled with the ability to weight which router in the network handles the amount of or what type of packets is very desirable.
It is an object of the present invention to provide a network processor with a network routing table having entries that include one or more next hops in addition to cumulative probability data for each corresponding next hop.
It is another object of the present invention to provide a method of randomly generating next hop seed values associated with a packet to be forwarded in a network and determining which next hop is chosen based on cumulative probability data for each corresponding next hop and the randomly generated next hop seed values.
According to the invention, there is provided a system and method for forwarding packets in a network processor (NP) device comprising: providing entries in a packet forwarding table for mapping a destination address associated with a packet to be forwarded to multiple, weighted next hop options in a networking environment; computing a weighting parameter based on data associated with the packet to be forwarded; and, routing the packet via one of the multiple next hop option selected in accordance with the computed weighting parameter. Preferably, the computing step includes applying a hash function to data associated with the packet to be forwarded to generate a corresponding hash value associated with that packet. For instance, in the case of a networking environment that includes an IP network, the data associated with the packet may comprise an IP source address and IP destination address of the packet to be forwarded. Each of the mapped multiple next hop options for each table entry includes a corresponding threshold value. Thus, to determine which next hop is selected in a packet forwarding operation, a comparison is made between the computed hash value and each corresponding threshold value.
The features of providing the ability for a media-speed, bandwidth conserving network processor device to select from multiple next hop options in a packet forwarding operation and providing the ability to weight the probability of which next hop will be chosen is extremely advantageous.